package LeetCode.NumOffer;

/**
 * 数组中的逆序对
 * @author lumin
 * @date 2022/03/18 12:38
 **/
public class NumOffer51 {
    //直接比较，时间复杂度为O（N^2）
//    public int reversePairs(int[] nums) {
//        if(nums.length < 2){
//            return 0;
//        }
//        int i = 0;
//        int num = 0;
//        while(i < nums.length){
//            int j = i + 1;
//            while(j < nums.length){
//                if(nums[i] > nums[j]){
//                    num++;
//                }
//                j++;
//            }
//            i++;
//        }
//        return num;
//    }
    public int reversePairs(int[] nums) {
        //如果数组的长度小于等于0，数组中不可能存在逆序对
        if(nums.length <= 1){
            return 0;
        }
        return reversePairsHelper(nums,0,nums.length - 1);
    }

    /**
     * 此函数可以求出一个数组中的逆序对
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int reversePairsHelper(int[] nums, int l, int r) {
        if(l >= r){
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        int leftNum = reversePairsHelper(nums,l,mid);
        int rightNum = reversePairsHelper(nums,mid + 1,r);
        //说明数组中还存在逆序对
        if(nums[mid] > nums[mid + 1]){
            //创建一个merge方法来辅助求出逆序对
            return merge(nums,l,mid,r) + leftNum + rightNum;
        }
        return leftNum + rightNum;
    }

    private int merge(int[] nums, int l, int mid, int r) {
        //先创建一个临时数组
        int[] aux = new int[r - l + 1];
        //再将数组元素拷贝至临时数组中
        for (int i = 0; i < aux.length; i++) {
            aux[i] = nums[i + l];
        }
        int i = l;
        int j = mid + 1;
        int ret = 0;
        for (int k = l; k <= r; k++) {
            if(i > mid){
                nums[k] = aux[j - l];
                j++;
            }else if(j > r){
                nums[k] = aux[i - l];
                i++;
            }else if(aux[i - l] <= aux[j - l]){
                nums[k] = aux[i - l];
                i++;
            }else{
                //数组中存在逆序对，求个数为mid - l + 1；
                ret += (mid - i) + 1;
                nums[k] = aux[j - l];
                j++;
            }
        }
        return ret;
    }
}